package com.github.hgkmail.hello.leetcode101.pointer.tree;

import com.github.hgkmail.hello.leetcode101.base.CommonUtil;
import com.github.hgkmail.hello.leetcode101.base.TreeNode;

import java.util.ArrayList;
import java.util.List;

public class LC404SumOfLeftLeaves {
    public void dfs(TreeNode root, TreeNode prev, List<Integer> sum) {
        if (root==null) {
            return;
        }
        //后序遍历（从下到上），先走到最底部（空节点 叶子节点）
        dfs(root.left, root, sum);
        dfs(root.right, root, sum);

        if (root.left==null && root.right==null && prev!=null && prev.left==root) {
            sum.set(0, sum.get(0)+root.val);
        }
    }
    public int sumOfLeftLeaves(TreeNode root) {
        if (root==null) {
            return 0;
        }
        List<Integer> sum=new ArrayList<>();
        sum.add(0);
        dfs(root, null, sum);

        return sum.get(0);
    }

    public static void main(String[] args) {
        TreeNode root= CommonUtil.deserializeBinaryTree("3,9,#,#,20,15,#,#,7,#,#");
        System.out.println(new LC404SumOfLeftLeaves().sumOfLeftLeaves(root));
    }
}
